1. Field of the Invention
The invention relates to decoding convolutional codes and, more particularly, to Viterbi decoding.
2. Related Art
A convolutional code is a type of error correcting code that is routinely used for reliable communications of digital data over a noisy channel. Convolutional codes are, for example, commonly used within telecommunications applications, such as digital subscriber line (“DSL”), wireless 802.11, and ultra-wide band applications.
Viterbi decoding is one method of decoding data streams that have been encoded with a convolutional encoder. Viterbi decoding performs optimal error correction for a given code to improve coding gain and produce reliable results at a digital receiver. To achieve a high level of performance, Viterbi decoding requires significant processing time because for each decode step it performs a calculation for each possible state of the encoder.
In older designs for decoders, a data stream flows though fixed-function hardware circuits that include the logic to perform Viterbi decoding. However, to provide greater flexibility with respect to decoder development, it has become more common to use software to perform the various functions in a decoder. Unfortunately, implementation of the Viterbi decoding algorithm in software is a complex calculation. As a result, when using conventional instructions (e.g., add, compare, select, etc) it may take many cycles to decode a single data symbol.
Given the growing consumer demand for high speed communications, such as DSL services, one processor within a DSL modem may need to handle several megabits per second. The Viterbi decode process for each symbol can therefore represent a significant proportion of the total computational cost of the modem. With increasing workloads (in terms of total data traffic passing through such a modem), it becomes necessary to improve the efficiency of the Viterbi decode process.
What is needed are methods and systems for efficiently implementing a Viterbi decoder.